/** 
  *https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/565456030/
 * 2616. 最小化数对的最大差值
 * medium,  2024.9.14
 * 二分搜索
*/
//参考同组成员的代码

class Solution {  
public:  
    int minimizeMax(vector<int>& nums, int p) {  
        sort(nums.begin(), nums.end());  
        int n=nums.size()-1; 
        function check=[&](int max) {
            int ans=0,i=0;  
            while(i<n){
                if(nums[i+1]-nums[i]<=max) { 
                    ans++;  
                    i+=2;  
                }else{  
                    i++; 
                }  
            }  
            return ans>=p;  
        };  
        int l=0, r=nums[n]-nums[0];//上界查找
        while(l<r){  
            int mid=l+(r-l)/2;  
            if(check(mid)){  
                r=mid; // 更新右边界  
            } 
            else{  
                l=mid+1; // 更新左边界
            }  
        }
        return l;  
    }  
};
